package com.tarena.day050;
import java.util.Arrays;
public class SortDemo {
  public static void main(String[] args) {
    int[] ary = {7,8,5,1,3};
    //selectionSort(ary);
    //bubbleSort(ary);
    insertSort(ary);
    System.out.println(Arrays.toString(ary));
  }
  /** 插入式排序 */
  public static void insertSort(int[] ary){
    int i,j,k;
    for(i=1; i<ary.length; i++){
      k = ary[i];//取出i对应的元素
      System.out.println("取出i:"+i+"元素k:"+k);
      //找到位置
      for(j=i-1; j>=0 && k<ary[j]; j--){
        System.out.print(Arrays.toString(ary)); 
        System.out.print(i+" "+j+" "+k+" "+ary[j]); 
        System.out.print("移动[j]->[j+1]"); 
        ary[j+1]=ary[j];//向后移动
        System.out.println(); 
      }
      System.out.println("移动完成:"+Arrays.toString(ary)
          +"j:"+j);
      ary[j+1]=k;//插入取出的元素
      System.out.println("插入到j+1:"+(j+1)
          +Arrays.toString(ary));
    }
  }
  
  /** 冒泡排序 */
  public static void bubbleSort(int[] ary){
    for(int i=0; i<ary.length-1;i++){
      for(int j=0; j<ary.length-i-1; j++){
        System.out.print(Arrays.toString(ary));
        System.out.print(i+" ");
        System.out.print(j+" "+(j+1)+" ");
        System.out.print(ary[j]+" ");
        System.out.print(ary[j+1]+" ");
        System.out.print((ary[j]>ary[j+1])+" ");
        if(ary[j]>ary[j+1]){
          System.out.print(ary[j]+"<->"+ary[j+1]);
          int t = ary[j];
          ary[j]=ary[j+1];
          ary[j+1]=t;
        }
        System.out.println(); 
      }
    }
  }
  /** 选择排序 */ 
  public static void selectionSort(int[] ary){
    for(int i=0; i<ary.length-1; i++){
      for(int j=i+1; j<ary.length; j++){
        if(ary[i]>ary[j]){
          int temp = ary[j];
          ary[j] = ary[i];
          ary[i] = temp;
        }
      }
    }
  }
}
